package 中等.动态规划.其他;

import java.util.Arrays;

/**
 * 给出一个单词数组 words ，其中每个单词都由小写英文字母组成。
 * 如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个
 * 字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的 前身 。
 * 例如，"abc" 是 "abac" 的 前身 ，而 "cba" 不是 "bcad" 的 前身
 * 词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word1 
 * 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的 单词链 。
 * 从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-string-chain
 */
public class 最长字符串链_1048 {

    public static void main(String[] args) {

        System.out.println(longestStrChain(new String[]{"ksqvsyq", "ks", "kss", "czvh", "zczpzvdhx", "zczpzvh", "zczpzvhx", "zcpzvh", "zczvh", "gr", "grukmj", "ksqvsq", "gruj", "kssq", "ksqsq", "grukkmj", "grukj", "zczpzfvdhx", "gru"}));

    }

    /**
     * 排序+动态规划+双指针
     * 1，长度较长的字符串的前身一定是长度比它小 1 的字符串，可以先根据字符串长度进行排序
     * 2，动态规划
     * 子问题：
     * dp[i] 表示以字符串 words[i] 结尾的最长词链是多少
     * 状态转移方程
     * dp[i] = Math.max[dp[i],dp[j]+1] (j < i,且 words[j].len+1 = words[i]，且 words[j] 是 words[i] 的前身)
     * 初始化值
     * dp[i] = 1 ，词链最短为 1
     * 3，双指针判断 j 是否是 i 的前身
     */
    public static int longestStrChain(String[] words) {
        int ans = 1;
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        int[] dp = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0 && words[j].length() + 1 >= words[i].length(); j--) {
                if (words[j].length() == words[i].length()) continue;
                if (isPre(words[j], words[i])) {

                    dp[i] = Math.max(dp[i], 1 + dp[j]);

                    ans = Math.max(ans, dp[i]);
                }
            }
        }
        return ans;
    }

    private static boolean isPre(String preStr, String str) {
        boolean hasOneDiff = false;
        int idx1 = 0, idx2 = 0;
        while (idx1 < preStr.length()) {
            if (preStr.charAt(idx1) == str.charAt(idx2)) {
                idx1++;
                idx2++;
                continue;
            }

            if (hasOneDiff) return false;

            idx2++;
            hasOneDiff = true;
        }
        return true;
    }

}
